﻿#define _CRT_SECURE_NO_WARNINGS 1

#include"Heap.h"

void test()
{
	HP hp;
	HPIint(&hp);
	HPPush(&hp, 6);
	HPPush(&hp, 4);
	HPPush(&hp, 8);
	HPPush(&hp, 10);
	
	//HPPop(&hp);
	//HPPop(&hp);
	//HPPop(&hp);
	//HPPop(&hp);

    while (!HPEmpty(&hp))
	{
		printf("%d ", HPTop(&hp));
		HPPop(&hp);//取栈顶就要删除栈顶，不然会一直循环
	}
	HPDesTroy(&hp);
}
///////////////////////////////////////////////
//1.堆排序
//给一组数组建成大堆，再升序，升序就是排列有序的小堆
//给一组数组建成小堆，再降序，降序就是排列有序的大堆
// 
//方法一：基于已有数组建堆、取堆顶元素完成排序版本
//该方法有⼀个前提，必须提供有现成的数据结构堆，没有借助堆的算法思想来
//void test01()
//{
//	int arr[] = { 17,20,10,13,19,15 };
//	int n = sizeof(arr) / sizeof(arr[0]);
//	HP hp;
//	HPIint(&hp);
//	//调用堆来对数组建堆
//	for (int i = 0; i < n; i++)
//	{
//		HPPush(&hp, arr[i]);
//	}
//	int i = 0;
//	while (!HPEmpty(&hp))
//	{
//		arr[i++] = HPTop(&hp);//取堆顶数据
//		HPPop(&hp);
//	}
//	//打印堆
//	for (int i = 0; i < n; i++)
//	{
//		printf("%d ", arr[i]);
//	}
//}

//void Swap(int* x, int* y)
//{
//	int tmp = * x;
//	* x = * y;
//	*y = tmp;
//}

//方法二：冒泡排序的写法，方法一没有借助堆的算法思想
//void BubbleSort(int* arr, int n)
//{
//	for (int i = 0; i < n; i++)
//	{
//		int exchange = 0;//用来判断真假，先设假，如果执行下去成功了就为1(真)
//		for (int j = 0; j < n - i - 1; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				exchange = 1;
//				Swap(&arr[j], &arr[j + 1]);
//			}
//		}
//		if (exchange == 0)
//		{
//			break;
//		}
//	}
//}
// 
// 方法三：数组建堆，⾸尾交换，交换后的堆尾数据从堆中删掉，将堆顶数据向下调整选出次⼤的数据
void HeapSort(int* arr, int n)
{
	//用给的数组来建堆
	//子结点：n-1  父节点：(n-1-1)/2
	//建小堆，排降序：用向下调整算法
	//for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	//{
	//	AdjustDown(arr, i, n);
	//}

	//建大堆，排升序；用向上调整算法
	for (int i = 0; i < n; i++)
	{
		AdjustUp(arr, i);
	}

	int end = n - 1;
	while (end>0)//最后一个下标要>0才行，不然会越界
	{
		Swap(&arr[0], &arr[end]);
		AdjustDown(arr, 0, end);
		end--;
	}
}


//void HeapSort(int* arr, int n)
//{
//	//根据给定的arr来进行建堆
//	//child:n-1  parent:(n-1-1)/2
//	////向下调整算法建堆
//	//for (int i = (n - 1 - 1) / 2; i >= 0; i--)//O(n)
//	//{
//	//	AdjustDown(arr, i, n);//O(logn)
//	//}
//
//	//向上调整建堆
//	for (int i = 0; i < n; i++)
//	{
//		AdjustUp(arr, i);
//	}
//
//	//堆排序
//	//排升序---建大堆
//	//排降序---建小堆
//	int end = n - 1;
//	while (end > 0)
//	{
//		Swap(&arr[0], &arr[end]);
//		AdjustDown(arr, 0, end);
//		end--;
//	}
//}
///////////////////////////////////////////////
//2.TopK问题：在实现这个问题之前，要创建一个有随机数的文件
// 
// 扩：解释srand
// 1.srand调用的是线性同余法算法(一种常用的伪随机数生成算法)
// 2.它会根据传递的参数设置一个起点或“种子”，这个种子值决定了后续生成的随机数序列
// 3.用srand(time(0))来调用，程序会利用当前时间作为种子值
// 4.这种做法可以确保每次运行时，能随机生成不同的随机数序列
// 5.srand与rand函数配合使用
// 6.确保数据不可预测性
//
//void CreateNDate()
//{
//	// 造数据
//	int n = 100000;
//	srand(time(0));
//	const char* file = "data.txt";
//	FILE* fin = fopen(file, "w");
//	if (fin == NULL)
//	{
//		perror("fopen error");
//		return;
//	}
//	for (int i = 0; i < n; ++i)
//	{
//		int x = (rand() + i) % 1000000;
//		fprintf(fin, "%d\n", x);
//	}
//	fclose(fin);
//}
//
//void TopK()
//{
//	int k = 0;
//	printf("请输入K：");
//	scanf("%d", &k);
//	const char* file = "data.txt";
//	FILE* fout = fopen(file, "r");
//	if (fout == NULL)
//	{
//		perror("fopen error");
//		exit(1);
//	}
//	//找最大的前K个数，建小堆
//	int* minHeap = (int*)malloc(sizeof(int) * k);
//	if (minHeap == NULL)
//	{
//		perror("malloc fail!");
//		exit(2);
//	}
//	//读取文件中前K个数据建堆
//	for (int i = 0; i < k; i++)
//	{
//		fscanf(fout, "%d", &minHeap[i]);
//	}
//	//建堆
//	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
//	{
//		AdjustDown(minHeap, i, k);
//	}
//	//遍历剩下的n-k个数据，跟堆顶比较，谁大谁入堆
//	//调整堆
//	int x = 0;
//	while (fscanf(fout, "%d", &x) != EOF)
//	{
//		if (x > minHeap[0])
//		{
//			minHeap[0] = x;
//			AdjustDown(minHeap, 0, k);
//		}
//	}
//	for (int i = 0; i < k; i++)
//	{
//		printf("%d ", minHeap[i]);
//	}
//	fclose(fout);
//}

void CreateNDate()
{
	int n = 100000;//表示生成的随机数的数量
	srand(time(0));
	const char* file = "data.txt";//定义文件指针
	FILE* fin = fopen(file, "w");//打开文件
	//当文件打为空，就打开失败
	if (fin == NULL)
	{
		perror("fopen error");
		return;
	}
	//用i来遍历，进行打印
	for (int i = 0; i < n; i++)
	{
		//生成一个随机数x，计算方式为 (rand() + i) % 1000000
		int x = (rand() + i) % 100000;
		fprintf("fin,%d\n", x);
	}
	//关闭文件指针:调用 fclose 函数，确保所有生成的数据都已正确写入文件，然后关闭文件指针
	fclose(fin);
}

void TopK()
{
	//要取数据中前k个数
	int k = 0;
	printf("请输入k：");
	scanf("%d", &k);

	//调用文件，读取文件
	const char* file = "data.txt";
	FILE* fout = fopen(file, "r");
	if (fout == NULL)
	{
		perror("fout open");
		exit(1);
	}

	//在文件中扩容,为建堆增加空间
	int* minHeap = (int*)malloc(sizeof(int)* k);
	if (minHeap == NULL)
	{
		perror("malloc fail");
		exit(2);
	}

	//读取前k个数据
	for (int i = 0; i < k; i++)
	{
		//使用 fscanf(fout, "%d", &minHeap[i]) 调用标准格式说明符库函数 fscanf，
		//它从文件中读入一个整数值，并将其存储在 minHeap 数组的第 i 个位置
		fscanf(fout, "%d", &minHeap[i]);
	}

	//对前k个数进行建堆，这一组数据中，最后一个数下标为k-1，则求父节点为(k-1-1)/2
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(minHeap, i, k);
	}

	//遍历剩下n-k个数据，再把遍历中的数据一个一个拿去跟堆顶比较，n-k中的数据大就入堆顶，小就不入继续往后遍历
	int x = 0;
	while (fscanf(fout, "%d", &x) != EOF)
	{
		if (x > minHeap[0])
		{
			minHeap[0] = x;
			AdjustDown(minHeap, 0, k);
		}
	}

	//打印堆
	for (int i = 0; i < k; i++)
	{
		printf("%d ", minHeap);
	}
}

int main()
{
	//test();
	//test01();//方法一
	//int arr[] = { 17,20,10,13,19,15 };
	//int n = sizeof(arr) / sizeof(arr[0]);
	////BubbleSort(arr, n);//方法二
 //   HeapSort(arr, n);
	//for (int i = 0; i < n; i++)
	//{
	//	printf("%d ", arr[i]);
	//}
	//CreateNDate();
	TopK();
	return 0;
}